package cn.hdr.train.hash;

/**
 * 1.初始容量自动向上调整为 2^n
 * 2.使用再线性寻址法解决 hash冲突，
 * 3.已实现自动扩容
 * @author: hdr
 * @date: 2020-07-07 15:22
 */
public class HashTableF<T,V> {

    static class Node<T,V>{
        private T key;
        private V value;
        private int hash;
        Node(T key,V value){
            this.key = key;
            this.value = value;
        }
    }

    private Node<T,V>[] table;

    private int size;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    public HashTableF(int capacity){
        if (capacity < 0)
            throw new IllegalArgumentException("capacity is error");
        table = new Node[tableSizeFor(capacity)];
    }

    public V get(T key) {
        if(key == null)
            return null;
        int nh = key.hashCode();
        int index  = nh & (table.length - 1);
        for (;;index = nextIndex(index)) {
            Node<T,V> node = table[index];
            if(node == null){
                return null;
            }else if(node.key.equals(key)){
                return node.value;
            }
        }

    }

    /**
     * copy from HashMap#tableSizeFor()
     */
    final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    public V put(T key,V value){
        if (key == null || value == null)
            throw new IllegalArgumentException("K,V must be not null");

        int nh = key.hashCode();
        int index  = nh & (table.length - 1);
        for (;;index = nextIndex(index)) {
            Node<T,V> oldNode = table[index];
            if(oldNode == null){
                Node<T,V> newNode = new Node<>(key,value);
                newNode.hash = nh;
                table[index] = newNode;
                size++;
                resize();
                return null;
            }else if(oldNode.key.equals(key)){
                V oldValue = oldNode.value;
                oldNode.value = value;
                return oldValue;
            }
        }
    }

    void resize(){
        if(size < table.length)
            return;

        //扩容，2倍扩容
        @SuppressWarnings({"unchecked"})
        Node<T,V>[] newtable = (Node<T,V>[])new Node[table.length << 1];
        for (Node<T, V> oldNode : table) {
            int newIndex = oldNode.hash & (newtable.length - 1);
            for (;;newIndex = nextIndex(newIndex)) {
                Node<T, V> oldnowNode = newtable[newIndex];
                if (oldnowNode == null) {
                    newtable[newIndex] = oldNode;
                    break;
                }
            }
        }
        table = newtable;
    }

    public V delete(T key){
        if (key == null)
            return null;
        int nh = key.hashCode();
        int index  = nh & (table.length - 1);
        for (;;index = nextIndex(index)) {
            Node<T,V> oldNode = table[index];
            if(oldNode == null){
                return null;
            }else if(oldNode.key.equals(key)){
                V oldValue = oldNode.value;
                table[index] = null;
                size--;
                //调整原来 hash冲突分配的位置
                reHash(index);
                return oldValue;
            }
        }
    }

    /**
     * 假如容量64
     * 插入 (0,0) ， (64,64) ， (128,128)。  那么产生了3个冲突。
     * 0    1   2   3   4   ...
     * 0    64  128
     * 现在删除 0，
     * 0    1   2   3   4   ...
     * NULL 64  128
     * 不进行rehash的话，get(64) 将为 NULL
     */
    private void reHash(int index){
        Node<T,V> e;
        int i;
        for (i = nextIndex(index);
             (e = table[i]) != null;
             i = nextIndex(i)){

            int h  = e.hash & (table.length - 1);
            if (h != i) {
                table[i] = null;

                while (table[h] != null)
                    h = nextIndex(h);
                table[h] = e;
            }
        }
    }

    private int nextIndex(int i) {
        return ((i + 1 < table.length) ? i + 1 : 0);
    }

    public int size(){
        return size;
    }

    public static void main(String[] args) {
        HashTableF<Integer,Integer> tableF = new HashTableF<>(4);

        System.out.println("PUT: " + tableF.put(99,52));
        System.out.println("PUT: " + tableF.put(5,35));
        System.out.println("PUT: " + tableF.put(7,52));
        System.out.println("PUT: " + tableF.put(38,72));
        System.out.println("PUT: " + tableF.put(0,32));
        System.out.println("PUT: " + tableF.put(64,19));

        System.out.println("PUT: " + tableF.put(0,6));
        System.out.println("GET: " + tableF.get(0));
        System.out.println("GET: " + tableF.get(64));

        System.out.println("DELETE: " + tableF.delete(0));
        System.out.println("GET: " + tableF.get(0));
        System.out.println("GET: " + tableF.get(64));
        System.out.println("SIZE: " + tableF.size());

    }
}